Thuật toán Pledge Thuật toán tìm đường đi trong mê cung

Ví dụ thuật toán giúp vượt qua vật cản hình chữ "G": quay ngược kim đồng hồ là chiều dương, quay cùng chiều kim đồng hồ là chiều âm. Các số liệu tương ứng với từng lần quay.

Nếu mê cung có các tường rời nhau, đồng thời lối vào lối ra của mê cung nằm trên tường bao của mê cung, thì thuật toán bám tường vẫn có thể tìm được đường ra. Tuy nhiên, nếu điểm vào nằm bên trong mê cung và tách rời khỏi lối ra, thì bám theo tường sẽ chỉ có thể đi thành 1 vòng cục bộ và không tìm được lối ra. Đối với trường hợp này, thuật toán Pledge (được đặt theo tên của Jon PledgeExeter) có thể giải quyết được vấn đề.[3]

Giải thuật Pledge được thiết kế để vượt qua vật cản, bằng cách chọn một hướng đi bất kỳ. Khi gặp vật cản, thì chuyển sang di chuyển bám theo tường dọc theo vật cản, kết hợp với đếm góc quay. Sau khi bám tường và quay mà trở về lại đúng hướng đi ban đầu đồng thời tổng góc đã quay bằng '0' (zero) thì tức là đã vượt qua khỏi vật cản, thì không cần bám tường nữa và tiếp tục di chuyển theo hướng ban đầu đã chọn.

Chỉ thoát khỏi bám theo tường khi thỏa mãn cả hai điều kiện: "hướng hiện tại trùng với hướng ban đầu" và "tổng số góc đã quay bằng '0'". Điều này là cần thiết để giúp di chuyển vòng qua vật cản phức tạp ví dụ như vật cản hình chữ "G" như trong hình. Ở vị trí +360o, robot có hướng di chuyển cùng hướng ban đầu, nếu bỏ bám tường bên phải mà tiếp tục di chuyển thẳng thì sẽ đi vào 1 vòng lặp mà không thoát ra được. Thay vào đó, nếu tiếp tục bám vào tường phải và thực hiện quay cho đến khi tổng góc quay là '0' thì sẽ thoát ra khỏi vật cản.

Tài liệu tham khảo

WikiPedia: Thuật toán tìm đường đi trong mê cung http://books.google.com/books?id=m3QTSMYm5rkC&pg=P... http://www.mazeworks.com/mazegen/ http://www.youtube.com/watch?v=FkueaIT6RSU&NR=1 http://www.youtube.com/watch?v=jhL8uELbVIM http://www.youtube.com/watch?v=yqZDYcpCGAI http://www.astrolog.org/labyrnth/algrithm.htm#solv... http://www.cb.uu.se/~cris/blog/index.php/archives/... https://www.youtube.com/watch?v=IIBwiGrUgzc https://www.youtube.com/watch?v=k1tSK5V1pds